package cn.edu.njust.alg.leetcode;

/**
 * 创建时间：2015年6月15日 上午11:47:37 项目名称：AlgorithmExercise
 * 
 * @author Zhou Xiumin
 * @version 1.0
 * @since JDK 1.7.0_21 文件名称：Leetcode_0_t.java 类说明：
 */
public class Leetcode_130_Surrounded_Regions {

	public static void dfs(char[][] board, boolean[][] visited, int i, int j) {
		visited[i][j] = true;
		int[][] dir = { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };
		int row = board.length;
		int col = board[0].length;
		int in, jn;
		for (int k = 0; k < dir.length; k++) {
			in = i + dir[k][0];
			jn = j + dir[k][1];
			if (in >= 0 && in < row && jn >= 0 && jn < col
					&& board[in][jn] == 'O' && !visited[in][jn]) {
				dfs(board, visited, in, jn);
			}
		}

	}

	public static void solve(char[][] board) {
		if (board == null || board.length <= 1) {
			return;
		}
		boolean[][] visited = new boolean[board.length][board[0].length];
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length; j++) {
				if (i * j == 0 || i == board.length - 1
						|| j == board[0].length - 1) {
					if (board[i][j] == 'O' && !visited[i][j]) {
						dfs(board, visited, i, j);
					}
				}
			}
		}
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length; j++) {
				if (board[i][j] == 'O' && !visited[i][j]) {
					board[i][j] = 'X';
				}
			}
		}

	}

	public static void main(String[] args) {
		char[][] board = { "XOXX".toCharArray(), "OXOX".toCharArray(),
				"XOXO".toCharArray(), "OXOX".toCharArray(),
				"XOXO".toCharArray(), "OXOX".toCharArray() };
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length; j++) {
				System.out.print(board[i][j]);
			}
			System.out.println();
		}
		solve(board);
		System.out.println();
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length; j++) {
				System.out.print(board[i][j]);
			}
			System.out.println();
		}
	}

}
